For merges, \(N_1 = N_2 = 10,000\) generates 100M comparisons across each of \(k\) linkage fields.

Deduplication: 50M comparisons.

Solution: Some observations are almost certainly not matches, so we don’t need to compare them.

Solution: Know your data well. Examine large clusters, esp. those with partial matches.

2. Define blocking rules

3. Define comparison criteria

3a. Train an unsupervised probabilistic model?

4. Match by applying comparison criteria to blocked data

5. Resolve matches into underlying clusters (people, entities, etc.)

6. Generate canonical output

Some approaches blend these steps together (say, redefine comparison criteria iteratively based on match quality).

• Removing punctuation and special characters (accents, etc.)
  • stringr::stri_trans_general in R.
  • But are you sure?

Addresses as strings… in two stages:

• Parsing into constituent components (house number, street name, …)
• Standardization of each component (“STREET” to “ST”)

• USA ZIP codes are easy, but don’t forget the northeast
  • Use stringr::str_pad()
  • str_pad('8540', width = 5, side = 'left', pad = '0') == '08540'

Addresses are very weird. Please do not attempt to standardize them on your own unless you are willing to dedicate a lot of time to building your own tool.

Or… use any (other) geocoder.

Please don’t ever pay for an address parser or geocoder (US only).

Geocoding converts messy address strings into structured lat/long coordinates. This means:

• You can compare geospatial distance and (or instead of) address strings
• Geocodes are standardized: misspellings, abbreviations, etc. all collapse to same coordinates
• Geohashes or spatial indices (like H3) become natural blocking keys

You can parallelize batches and the Census API will, generally, cooperate.

Considerations:

• You will almost certainly drop comparisons between matches.
  • Inherent tradeoff between tractability and false negatives.
  • Recall in real-world examples is often < 0.75.
• Typically the cleanest/most reliable field(s) in your dataset.
• Hopefully high cardinality (GEOIDs >> ZIP codes)
• Blocking fields are often skewed (state, first name, last name)
• Required specificity determined by data size, skew, cardinality of blocking vars, and compute resources.
• Join key types typically affect performance quite a bit. Avoid strings if possible.

KNOW YOUR DATA WELL ENOUGH TO SELECT GOOD BLOCKS.

11.7 trillion comparisons.

What if we block on gender?

5.9 trillion comparisons.

What if we block on gender and first initial?

513 billion comparisons.

What if we block on gender and first name?

47 billion comparisons (~12min w/ DuckDB’s Jaro-Winkler)

Get creative!

FROM dfA l
INNER JOIN dfB r
ON (l.zip = r.zip AND l.first = r.first)
  OR (coalesce(l.gender = r.gender, true) AND l.zip = r.zip AND l.last = r.last)
  OR (coalesce(l.gender = r.gender, true) AND l.first[1] = r.first[1] AND l.last[1] = r.last[1])
  OR (l.zip = r.ZIP AND l.last = r.last)
  [ ... ]

• Gender (usually imputed from SSA records)
  • Madison between 1980 and 2000

• Names (or their substrings – e.g., first letters)
  • Beware misspellings early in strings
  • What about nicknames? (more later)
    • (l.first IN r.first_nicknames) OR (r.first IN l.first_nicknames)
  • Beware last name changes by gender

Be sure you handle missingness as intended.

• Joining on nulls?

• Convert name strings to phonetic representations (soundex, [double-]metaphone)
  • {JOHN, JHON, KOHN} maps to {J500, J500, K500}

• Canopy clustering

• Locally sensitive hashing (later) for strings or points

• Cosine similarity/nearest neighbors with semantic embeddings for strings (later)

What about geospatial data?

Levenshtein: Number of insertions, deletions, substitutions

Damerau-Levenshtein: same, but with transpositions

Jaccard (bag of n-grams): \[1 - \frac{|S_1 \cap S_2|}{|S_1 \cup S_2|}\]

Jaro: \(\in [0,1]\), function of matching characters and their positions, transpositions

Jaro-Winkler: Upweights matching at beginning of string - Most common for names (developed for them)

Phonetics (soundex, [double-]metaphone) … and many others

More recently, token sort ratio functions (e.g., via RapidFuzz)

Notes:

stringdist::stringsim('NEW YORK CITY', 'NYC', 'jaccard')     # 0.27
stringdist::stringsim('ELIZABETH', 'BETH', 'jw')             # 0.45
stringdist::stringsim('5th AVE', '6th AVE', method='jw')     # 0.90
## but...
stringdist::stringsim('FIFTH AVE', 'SIXTH AVE', method='jw') # 0.85

How to handle addresses?

This assumes you know the criteria that defines a match (well enough).

But what if you don’t? (Or what if you want a posterior probability?)

Remember! What’s different here vs. base R?

Why does jaro_winkler_similarity(...) work in the call to filter()?

Most commonly, connected components

• Observations are nodes, matches are edges
• Find all (connected) clusters
• Requires discretizing match status from posteriors

Can implement other algorithms (with probabilities as IPWs) if computationally feasible (e.g., label propagation).

• See community detection algorithms in the onager extension for DuckDB here.

In DuckDB:

install onager from community;
load onager;

create table edges as
select *
from (values (1::bigint, 2::bigint),
             (2, 3),
             (3, 1),
             (4, 5),
             (5, 6)) t(src, dst);

from onager_cmm_components((select src, dst from edges))

(What’s the answer?)

See here for manual coding example in Python/DuckDB

Overclustering is particularly important for descriptive relationships…

Some options for inference:

• Naive bootstrap for records
• Posteriors (in probabilistic approach) as sampling or propensity weights
• Quickly becoming clear why connected components is dispensing with a lot of potentially useful information…
• There are principled ways of doing this

Benefit (0): You don’t define all of the possible “match” criteria combinations across linkage fields or label any label data.

Benefit (1): We formalize assumptions necessary to incorporate posterior match probabilities as weights when merged data is outcome or explanatory variable.

Benefit (2): We can incorporate prior match probabilities from existing information (e.g., migration rates, name frequency weighting).

You must specify blocks, comparison criteria/levels, posterior threshold for a match (sometimes), and (optional) priors.

Several robust, efficient implementations across languages.

Similarity between \(i \in A, j \in B\) in field \(k\) is \(S_k(i,j)\), typically \(\in [0,1]\).

We coarsen this similarity to an agreement pattern \(\gamma_k(i,j)\) where: \[\gamma_k(i,j) = \begin{cases} 2 & S_k(i,j) \geq \tau_2 \\ 1 & \tau_1 \leq S_l < \tau_2 \\ 0 & \text{otherwise} \end{cases}\]

This is generalizable to distance metrics, discrete metrics (e.g., Levenshtein), etc.

For \(i, j\), we have \(\boldsymbol{\gamma}(i,j) = \{\gamma_1(i,j), ..., \gamma_k(i,j)\}\) with some number of agreement levels \(L_k\).

Let \(m\in \{0,1\}\) be the (unknown) match status for \(i,j\), which is distributed

\[ M(i,j) \stackrel{iid}{\sim} \text{Bernoulli}(\lambda) \]

Assume that the probability of each agreement level is distributed

\[\gamma_k(i,j) | M(i,j) = m \stackrel{indep}{\sim} \text{Discrete}(\boldsymbol{\pi}_{km})\]

\[\mathbb{P}(M_{ij} = 0 | \xi_{ij} \geq S) = \frac{\sum_{i=1}^{N_A}\sum_{j=1}^{N_B}\boldsymbol{1}\{\xi_{ij} \geq S \}(1-\xi_{ij})}{\sum_{i=1}^{N_A}\sum_{j=1}^{N_B}\boldsymbol{1}\{\xi_{ij} \geq S \}}\]

False negative rate (1 - recall):

\[\mathbb{P}(M_{ij} = 1 | \xi_{ij} \geq S) = \frac{\sum_{i=1}^{N_A}\sum_{j=1}^{N_B}\boldsymbol{1}\{\xi_{ij} < S \}}{\lambda N_A N_B}\]

Most people just apply a threshold (the default is 0.85) and move on.

Recommendation: investigate some pairs in each observed \(\boldsymbol{\gamma}\) combination near some \(S_1\) and apply post-hoc filtering. (Recall household overclustering problem.)

• Usually you will estimate parameters on a random sample

• You iterate over the blocks.
  • blockData() is mostly a split into lists

• Summary functions yield aggregate estimated FDR, FNR for a few common posterior thresholds

1. You want model diagnostic visualization.

2. You need more flexible blocking, comparison field/level definitions, etc.

3. You need to scale.

• fastLink: 300k obs. in 400 min (2.8 GHz Intel i7 (8 core), 8GB RAM) in ~2017
• splink: 7M obs. (1B comparisons) in 20 min (c6g.2xlarge, 8vCPU, 16GM RAM) in ~2024
  • Latter includes all blocking, training, prediction, and clustering (source)
  • Even faster now.
  • Supports DuckDB or Spark backends.

• Estimate \(\lambda\), \(\mathbb{P}(\text{two random records match})\), via custom deterministic rules that define matches with (near-)certainty (e.g., SSN, DOB if you have it, or name + address, etc.)

• Estimate \(\mathbb{u}_k\) probabilities, \(\mathbb{P}_{i,j}(\text{observing this comparison level} | \text{not a match})\), via random sampling (given that any two random record are almost guaranteed not to match)

• Estimate \(\mathbb{m}_k\) probabilities, \(\mathbb{P}_{i,j}(\text{observing this comparison level} | \text{match})\), via EM algorithm with multiple passes (each with a different blocking rule set)
  • Idea: Increase proportion of actual matches in our training blocking rules to improve parameter estimation.

• Use more lenient rules in predict() stage, where comparisons are cheap and parallelization scales ~linearly

Expectation step: Use the estimated model parameters to predict which record comparisons are matches

Maximisation step: Use the predictions to re-estimate the model parameters

See Linacre (here) for source, more info.

Dict-based (still supported):

comparison = {
  "output_column_name": "field",
  "comparison_levels": [...]
}

Blend (most likely):

CustomComparison(
  output_column_name="first_name",
  comparison_levels=[
      cll.NullLevel("first_name"),
      cll.ExactMatchLevel("first_name").configure(tf_adjustment_column="first_name"),
      cll.ExactMatchLevel("soundex_first_name").configure(tf_adjustment_column="soundex_first_name"),
      cll.ElseLevel()
])

If you have 3 blocking rules, one with salting_partitions = 1: \(1 + 1 + 2 = 4\) partitions

Then: base parallelism (9) \(\times\) 4 = ~36 parallel tasks

Key point: the size of the blocks matters for parallelism and memory. Salting splits large blocks into smaller partitions to improve throughput.

This is a miserable problem, usually compounded by a lack of blocking variables.

“J.P. Morgan Chase” vs. “JPMORGON” vs. “JPM”

• "JP MORGAN" and "CHASE BANK" are the same company now, but were not before 2000.

• “FACEBOOK” vs. “META PLATFORMS, INC.”

There is a string similarity problem AND an information problem.

• (“Lexical similarity” vs. “semantic similarity”)

If we could create an \(n\)-dimensional representation of the string and incorporate outside information…

Libgober and Jerzak (2024, PSRM): LinkOrgs software and paper

Kaufman and Klevs (2022, Political Analysis): Adaptive Fuzzy String Matching

Idea: Capture both semantic and lexical similarity. A “supervised” model, but use LLMs to embed and label data.

1. Embed all (unique) strings in (single!) comparison field.
2. Respecting any (exact-match) blocks, compute \(N_A * N_B\) cosine (semantic) similarities.
3. Also compute lexical similarities (e.g., Jaro distance) for each of \(N_A * N_B\) pairs.
4. Labeling step: For pairs with highest semantic similarity, label “match” via LLM.
5. Fit model (logit, random forest, etc.) on training data.
6. Sample around “most uncertain” ( = 0.5) region and repeat Step 4.
7. Refit/repeat Steps 5-6 until convergence.
8. Merge datasets, spending any remaining LLM budget, then using probabilities to define match threshold that maximizes \(F_1\) score.

Two-stage pipeline — no training data, no API key required (runs locally):

1. Retrieval (blocking): Find top-\(k\) candidate matches from corpus for each query record.

• Dense (semantic) embeddings as in previous method.
• Sparse (lexical) embeddings via TF-IDF over n-grams.

2. Re-ranking (comparing): Cross-encoder model scores candidates \(\in [0,1]\).

For larger datasets, block first and match on detail fields:

results <- ensemble_link_blocked(
  query_blocks  = dfA$state,     # exact-match blocking key
  query_details = dfA$name,      # field for embedding comparison
  corpus_blocks  = dfB$state,
  corpus_details = dfB$name,
  ...
)

Recall that

\[J(C_1, C_2) = \frac{|C_1 \cap C_2|}{|C_1 \cup C_2|}\]

The pipeline:

1. Shingling → represent each string as a set
2. Min-hashing → compress sets into short signatures
3. LSH (banding) → generate candidate pairs from signatures

This gives us a way to block without exact matching — we can find candidate pairs that are approximately similar, without comparing every pair.

JOHN as 2-grams: {JO, OH, HN}

Now represent every string by its k-shingle set:

\(\text{Jaccard}(\texttt{JOHN}, \texttt{JOHNN}) = \frac{|\{\texttt{JO, OH, HN}\}|}{|\{\texttt{JO, OH, HN, NN}\}|} = \frac{3}{4}\)

• For short strings, pick small \(k \approx 5\)
• For longer strings, layer \(k\) so you don’t have all shingles in every string
• Optional: hash shingles again to improve storage — e.g., {JO, OH, HN} → {2, 1, 7}

With many unique shingles, this matrix is very sparse and requires a lot of memory to store.

Still \(\frac{N(N-1)}{2}\) pairwise comparisons. Can’t do this on one-hot encoded vectors at scale.

Idea: “hash” each column (i.e., each string’s one-hot encoding) so that the hashes all fit in memory.

Key property: for Jaccard similarity, we can find a hash \(h\) such that

\[J(C_1, C_2) \propto \Pr(h(C_1) = h(C_2))\]

This hash function is called the min-hash.

Why? For any random row, the pair \((S_1, S_2)\) is one of:

\[\Pr(P_i(S_1) = P_i(S_2)) = \frac{X}{X + Y}\]

which is exactly the Jaccard similarity.

So: similarity of \(S_1\) and \(S_2\) \(\approx\) fraction of hash functions in which their signatures agree.

As \(N_{\text{hashes}} \to \infty\), this converges to Jaccard.

But permutations and storage are both quite memory-intensive.

Tweak 1: Instead of \(N\) actual permutations, use \(N\) hash functions that map row numbers to buckets.

Example: \(h_1 = (x + 1) \bmod 5\), \(\quad h_2 = (3x + 1) \bmod 5\)

As long as the number of buckets is large enough to avoid too many collisions, this approximates random row permutations without actually permuting.

We can work string by string without storing the full one-hot matrix.

Tweak 2: Only examine \(M\) rows per hash function, where \(M \ll K\). This gives \(\sim K/M\) reduction in compute.

This is an approximation. For two random strings \(S_i, S_j\):

1. If both \(= 0\) \(\forall\) \(M\) rows → we learn nothing from this function
2. If only one \(= 0\) \(\forall\) \(M\) rows → we know they’re quite different (only one gets updated)

As long as case (1) is rare, this isn’t a serious problem — and we can spend the saved time computing more hash functions.

But still \(\binom{1\text{M}}{2} \approx 500\text{B}\) comparisons!

We could hash each signature to some value (and then block on that), but we’d only catch items with exactly the same signatures.

We need a way to find approximately matching signatures…

“Candidate” pairs: strings that have the same signature in at least one band.

How to find them? Hash each band’s signature to a bucket. Look at buckets with more than one item.

With \(b = 20, r = 5\), find pairs with Jaccard \(\geq 0.8\):

\[\Pr(C_1, C_2 \text{ match in one band}) = (0.8)^5 \approx 0.328\]

\[\Pr(\text{not similar in ANY band}) = (1 - (0.8)^5)^{20} \approx 0.00035\]

We miss ~1 in 3,000 true pairs.

This is an S-surve.

• Above the threshold: false negatives (pairs we missed)
• Below the threshold: false positives (non-matches flagged as candidates)

Didn’t cover: Euclidean LSH for vectors

A (0.1, 0.7, 0.001, 0.99)-sensitive LSH means that strings with similarity less than 0.1 will have a 0.1% chance of being compared, while strings with 0.7 similarity have a 99% chance of being compared.

band_width    n_bands
         5         26

   cluster          n
 1 LINDA     16451074
 2 SANDRA     8000394
 3 KAREN      7973116
 4 PAMELA     7548071
 5 HELEN      5752257
 6 MARY       5179872

   first   gender      N cluster
 1 LINDA   F      876697 LINDA  
 2 DIANE   F      368332 LINDA  
 3 JANE    F      154558 LINDA  
 4 DIANA   F      271258 LINDA  
 5 ANNE    F      168358 LINDA  
 6 DIANNE  F       58080 LINDA  
 7 ANNA    F      324602 LINDA  
 8 ANNIE   F       62001 LINDA  
 9 JANIS   F       27071 LINDA  
10 LILLIAN F       78254 LINDA  

SQL is sometimes the “lower level” language.

• Binette and Steorts, (Almost) All of Entity Resolution
  • Start here, particularly for newer methods.

• Marchant et al., d-blink: Distributed End-to-End Bayesian Entity Resolution